package algorithm_optimal_solution.LinkedList;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//两个单链表相交判断：只有两种情况，两种链表都有环，两种链表都无环。可以拆分成三个子问题。
//判断一个链表是否有环：设置一个slow慢指针和一个fast快指针，慢指针每次走一步，快指针每次走两步，当快指针遇到慢指针的时候即为环。
//              并且快指针从头开始每次走一步，再次遇到慢指针的时候即为入环节点。
//判断无环链表是否相交：找出两个链表的长度len1、len2，以及最后的节点end1、end2，end1!=end2即不相交。
//              较长的链表先走len1-len2或len2-len1步，然后一起走，第一次走到一起的节点即为第一个相交节点。
//判断有环链表是否相交：如果入环节点相等ring1==ring2，那么求解与无环链表相交判断类似，只是尾节点是ring1(ring2)。
//              反之，ring1第一次遇到ring2的节点即为第一个相交节点。
public class TwoLinkedListIfIntersect {

    static class Node{
        private int value;
        private Node node;

        public Node(int value,Node node){
            this.value = value;
            this.node = node;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getNode() {
            return node;
        }

        public void setNode(Node node){
            this.node = node;
        }
    }

    public void ifLinkedListIntersect(Node head1,Node head2){
        Node node1 = ifRing(head1);
        Node node2 = ifRing(head2);
        Node result = null;
        StringBuilder sb = new StringBuilder();
        if(node1 == null && node2 == null){
            result = ifNoRingIntersect(head1,head2);
            while(result != null){
                sb.append(result.getValue()).append(" ");
                result = result.getNode();
            }
        }else if(node1 != null && node2 != null){
            result = ifRingIntersect(head1, node1, head2, node2);
            if(result != null && node1 != node2){//有环入环节点不相等
                Node head = result.getNode();
                sb.append(result.getValue()).append(" ");
                while(head != result){
                    sb.append(head.getValue()).append(" ");
                    head = head.getNode();
                }
            }else if(result != null){//有环入环节点相等
                while(result != node1){
                    sb.append(result.getValue()).append(" ");
                    result = result.getNode();
                }
                sb.append(result.getValue()).append(" ");
                result = result.getNode();
                while(result != node1){
                    sb.append(result.getValue()).append(" ");
                    result = result.getNode();
                }
            }
        }
        System.out.println(sb);
    }

    //链表是否是环
    private Node ifRing(Node head){
        Node slow = head.getNode();
        Node fast = head.getNode().getNode();
        while(slow != fast){
            if(fast.getNode() == null || fast.getNode().getNode() == null){
                return null;
            }
            slow = slow.getNode();
            fast = fast.getNode().getNode();
        }
        fast = head;
        while(slow != fast){
            slow = slow.getNode();
            fast = fast.getNode();
        }
        return slow;
    }

    //有环链表是否相交
    public Node ifRingIntersect(Node head1,Node ring1,Node head2,Node ring2){
        Node node1;
        Node node2;
        if(ring1 == ring2){
            int n = 0;
            node1 = head1;
            node2 = head2;
            while(node1.getNode() != ring1){
                n++;
                node1 = node1.getNode();
            }
            while(node2.getNode() != ring2){
                n--;
                node2 = node2.getNode();
            }
            node1 = n > 0 ? head1 : head2;
            node2 = node1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while(n != 0){
                n--;
                node1 = node1.getNode();
            }
            while(node1 != node2){
                node1 = node1.getNode();
                node2 = node2.getNode();
            }
            return node1;
        }else{
            node1 = ring1.getNode();
            while(node1 != ring1){
                if(node1 == ring2){
                    return ring1;
                }
                node1 = node1.getNode();
            }
            return null;
        }
    }

    //无环链表是否相交
    public Node ifNoRingIntersect(Node head1,Node head2){
        int n = 0;
        Node node1 = head1;
        while(node1.getNode() != null){
            n++;
            node1 = node1.getNode();
        }
        Node node2 = head2;
        while(node2.getNode() != null){
            n--;
            node2 = node2.getNode();
        }
        if(node1 != node2){
            return null;
        }
        node1 = n > 0 ? head1 : head2;
        node2 = node1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while(n != 0){
            n--;
            node1 = node1.getNode();
        }
        while(node1 != node2){
            node1 = node1.getNode();
            node2 = node2.getNode();
        }
        return node1;
    }

    //5 7
    //34 12 23 29 32
    //5 7 34 16 13 3 8
    public static void main(String[] args)throws IOException {
        TwoLinkedListIfIntersect main = new TwoLinkedListIfIntersect();
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        String[] values = scanner.readLine().split(" ");
        int len = Integer.parseInt(values[0]);
        int twoLen = Integer.parseInt(values[1]);

        String[] numbers = scanner.readLine().split(" ");//链表1
        Node node = new Node(Integer.parseInt(numbers[len - 1]),null);
        Node ringNode = node;//最后一位
        for(int i = len - 2;i >= 0;i--){
            node = new Node(Integer.parseInt(numbers[i]),node);
        }

        String[] twoNumbers = scanner.readLine().split(" ");//链表2
        Node twoNode = new Node(Integer.parseInt(twoNumbers[twoLen - 1]),null);
        Node ringTwoNode = twoNode;//最后一位
        for(int i = twoLen - 2;i >= 0;i--){
            twoNode = new Node(Integer.parseInt(twoNumbers[i]),twoNode);
        }

        Node newRingNode = new Node(5,null);//相交部分
        Node tailNode = newRingNode;//最后一位
        for(int i = 4;i > 0;i--){
            newRingNode = new Node(i,newRingNode);
        }

        int random = (int)(Math.random() * 100) % 5;
        System.out.println(random);
        if(random == 0){//入环节点不相等的有环相交
            tailNode.setNode(newRingNode);
            ringNode.setNode(newRingNode);
            ringTwoNode.setNode(tailNode);
            main.ifLinkedListIntersect(node,twoNode);
        }else if(random == 1){//无环相交
            ringNode.setNode(newRingNode);
            ringTwoNode.setNode(newRingNode);
            main.ifLinkedListIntersect(node,twoNode);
        }else if(random == 2){//有环不相交
            ringNode.setNode(node);
            ringTwoNode.setNode(twoNode);
            main.ifLinkedListIntersect(node,twoNode);
        }else if(random == 3) {//无环不相交
            main.ifLinkedListIntersect(node,twoNode);
        }else if(random == 4){//入环节点相等的有环相交
            Node tempNode = new Node(56,null);
            Node tailTempNode = tempNode;
            for(int i = 55;i > 50;i--) {
                tempNode = new Node(i, tempNode);
            }
            tailNode.setNode(newRingNode);
            tailTempNode.setNode(newRingNode);
            ringNode.setNode(tempNode);
            ringTwoNode.setNode(tempNode);
            main.ifLinkedListIntersect(node,twoNode);
        }
    }
}
